/**
 * Author@ Cheng Feitian
 * Date: 2020-3-10
 * Description: 给定一个字符串描述的算术表达式，计算出结果值。
 * 输入字符串长度不超过100，合法的字符包括”+, -, *, /, (, )”，”0-9”，
 * 字符串内容的合法性及表达式语法的合法性由做题者检查。本题目只涉及整型计算。
 * Input Format: 输入算术表达式
 * Output Format: 计算出结果值
 */

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

#define STACK_SIZE 64   /* 栈大小 */
#define TOP_OF_STACK -1 /* 栈顶位置 */
typedef int ElemType;   /* 栈元素类型 */

typedef struct Stack
{
    int topOfStack;             /* 栈顶位置 */
    ElemType stack[STACK_SIZE]; /* 栈数组 */
} StackInfo_st;

static char priority[128] = {0}; /* 用于记录符号的优先级，存在空间浪费，可优化 */

bool stack_push(StackInfo_st *s, ElemType e);
bool stack_is_full(StackInfo_st *s);
bool stack_is_empty(StackInfo_st *s);
bool stack_pop(StackInfo_st *s, ElemType *e);
bool stack_pop(StackInfo_st *s, ElemType *e);
void priorityInit();
int priorityCompare(char op1,char op2);
bool exProcess(char *str, int *result);
bool doCal(StackInfo_st *nums, StackInfo_st *ops, int operator);

int main(void)
{
    /* 初始化 */
    char str[101];
    int result = 0;
    /* 主逻辑 */
    priorityInit();
    if (gets(str))
    {
        if (exProcess(str, &result))
            printf("%d\n", result);
    }

    return 0;
}

bool stack_push(StackInfo_st *s, ElemType e)
{
    bool status;
    if (stack_is_full(s))
    {
        status = false;
    }
    else
    {
        s->topOfStack++;
        s->stack[s->topOfStack] = e;
        status = true;
    }

    return status;
}

bool stack_is_full(StackInfo_st *s)
{
    bool status;

    if (s->topOfStack == STACK_SIZE - 1)
    {
        status = true;
    }
    else
    {
        status = false;
    }

    return status;
}

bool stack_is_empty(StackInfo_st *s)
{
    bool status;

    if (s->topOfStack == TOP_OF_STACK)
    {
        status = true;
    }
    else
    {
        status = false;
    }

    return status;
}

bool stack_pop(StackInfo_st *s, ElemType *e)
{
    bool status;
    if (stack_is_empty(s))
    {
        status = false;
    }
    else
    {
        *e = s->stack[s->topOfStack];
        s->topOfStack--;
        status = true;
    }

    return status;
}

bool stack_top(StackInfo_st *s, ElemType *e)
{
    bool status;
    if (stack_is_empty(s))
    {
        status = false;
    }
    else
    {
        *e = s->stack[s->topOfStack];
        status = true;
    }
    return status;
}

void priorityInit()
{

    /* 初始化各个符号的优先级，值越小，优先级越高 */
    priority['+'] = 4;
    priority['-'] = 4;
    priority['*'] = 3;
    priority['/'] = 3;
    priority['('] = 1;
    priority[')'] = 1;
}

int priorityCompare(char op1,char op2){
    return priority[op2] - priority[op1];
}

bool exProcess(char *str, int *result)
{
    /**
     * @brief 算法思想：中缀转后缀表达式
     * 1. 将字符串转换成后缀表达式，一个栈用来存储操作数，另一个栈用来存储操作符
     * 2. 操作符栈非空之前，弹出一个操作符，并弹出相应的操作数，运算后的结果压入操作数栈
     * 3. 重复第二步
     */
    bool status;

    if (str == NULL)
    {
        status = false;
    }
    /* 创建栈，用于保存数 */
    StackInfo_st nums;
    nums.topOfStack = TOP_OF_STACK;

    /* 创建栈，用于保存操作符 */
    StackInfo_st ops;
    ops.topOfStack = TOP_OF_STACK;

    /* 用于标记，判断上一个是否为数字 */
    int flag = 0;
    /* 用于将字符转化成数字 */
    int temp = 0;
    int operator;
    while (*str != 0)
    {
        if (isdigit(*str))
        {
            if (flag == 1)
            {
                stack_pop(&nums, &temp);
            }
            else
            {
                temp = 0;
            }
            flag = 1;
            temp = 10 * temp + *str - '0';
            stack_push(&nums, temp);
        }
        else if (*str == '/' || *str == '*' || *str == '+' || *str == '-')
        {
            flag = 0;
            while ((ops.topOfStack > TOP_OF_STACK) && (stack_top(&ops, &operator)) && '(' != operator && ')' != operator && (priorityCompare(*str,operator) <= 0))
            {
                if (!doCal(&nums, &ops, *str))
                {
                    status = false;
                }
            }
            stack_push(&ops, *str);
        }
        else if (*str == '(')
        {
            flag = 0;
            stack_push(&ops, *str);
        }
        else if (*str == ')')
        {
            flag = 0;
            while (stack_top(&ops, &operator) && operator!= '(')
            {
                if (!doCal(&nums, &ops, *str))
                {
                    status = false;
                }
            }
            stack_pop(&ops, &operator);
        }
        else
        {
            flag = 0;
        }
        str++;
    }
    while (!stack_is_empty(&ops) && !stack_is_empty(&nums))
    {
        if (!doCal(&nums, &ops, 0))
            status = false;
    }
    stack_pop(&nums, &temp);

    if (!stack_is_empty(&ops) || !stack_is_empty(&nums))
    {
        status = false;
    }

    if (stack_pop(&nums,&temp))
    {
        status = true;
    }
    *result = temp;

    return status;
}

bool doCal(StackInfo_st *nums, StackInfo_st *ops, int operator)
{
    int a, b;
    int result = 0;
    bool status = true;

    if (!stack_pop(&nums, &b))
    {
        status = false;
    }
    if (!stack_pop(&nums, &a))
    {
        status = false;
    }
    stack_pop(&ops, &operator);

    switch (operator)
    {
    case '+':
        result = a + b;
        stack_push(&nums, result);
        break;
    case '-':
        result = a - b;
        stack_push(&nums, result);
        break;
    case '*':
        result = a * b;
        stack_push(&nums, result);
        break;
    case '/':
        result = a / b;
        stack_push(&nums, result);
        break;
    default:
        break;
    }

    return status;
}
